#include "Struct.h"
mgraph initgraph() {
	mgraph c;
	FILE* f;

	// 尝试打开文件
	f = fopen("map.txt", "r");
	if (f == NULL) {
		perror("无法打开文件map.txt");
		// 返回一个默认初始化的图结构，可根据实际情况调整错误处理逻辑
		c.vexnum = 0;
		c.arcnum = 0;
		return c;
	}

	// 读取顶点个数和边个数
	if (fscanf(f, "%d %d", &c.vexnum, &c.arcnum) != 2) {
		perror("读取顶点个数和边个数失败");
		fclose(f);
		// 可以选择在这里输出更详细的错误信息并终止程序，或者尝试恢复程序到合理状态
		exit(EXIT_FAILURE);
	}

	// 检查顶点个数和边个数合法性，避免不合理的值导致后续数组越界等问题
	if (c.vexnum <= 0 || c.vexnum > 100 || c.arcnum < 0 || c.arcnum >(c.vexnum * (c.vexnum - 1) / 2)) {  // 边数最多为完全图的边数情况
		perror("顶点个数或边个数数据不合理");
		fclose(f);
		// 同样可以根据需求进行更详细的错误处理，这里选择终止程序
		exit(EXIT_FAILURE);
	}

	// 读取顶点信息
	for (int i = 1; i <= c.vexnum; i++) {

		if (fscanf(f, "%d", &c.vexs[i].position) != 1) {
			perror("读取顶点位置信息失败");
			fclose(f);
			exit(EXIT_FAILURE);
		}
		// 清除换行符或空格
		int ch;
		while ((ch = fgetc(f)) != '\n' && ch != EOF);

		if (fgets(c.vexs[i].name, sizeof(c.vexs[i].name), f) == NULL) {
			perror("读取顶点名称失败");
			fclose(f);
			exit(EXIT_FAILURE);
		}
		c.vexs[i].name[strcspn(c.vexs[i].name, "\n")] = '\0';  // 去掉换行符
		if (fgets(c.vexs[i].introduction, sizeof(c.vexs[i].introduction), f) == NULL) {
			perror("读取顶点简介失败");
			fclose(f);
			exit(EXIT_FAILURE);
		}
		c.vexs[i].introduction[strcspn(c.vexs[i].introduction, "\n")] = '\0';
	}

	// 初始化邻接矩阵
	for (int i = 1; i <= c.vexnum; i++) {
		for (int j = 1; j <= c.vexnum; j++) {
			c.arcs[i][j].adj = Infinity;
            c.arcs[1][2].adj = 100; c.arcs[2][11].adj = 250; c.arcs[6][12].adj = 300; c.arcs[7][14].adj = 175; c.arcs[7][4].adj = 150;
            c.arcs[3][11].adj = 150; c.arcs[3][2].adj = 200; c.arcs[4][6].adj = 250; c.arcs[8][14].adj = 200; c.arcs[10][12].adj = 150;
            c.arcs[12][4].adj = 150; c.arcs[14][4].adj = 450; c.arcs[15][9].adj = 200; c.arcs[9][10].adj = 150;
		}
	}
	for (int i = 1;i <= key;i++)//邻接矩阵是对称矩阵，对称赋值（无向图需要对称赋值） 
		for (int j = 1;j <= key;j++)
			c.arcs[j][i].adj = c.arcs[i][j].adj;
	return c;
}//initgraph
//2.查找景点在图中的序号
int locatevex(mgraph c, int v)//locatevex
{
	int i;
	for (i = 1;i <= c.vexnum;i++)
		if (v == c.vexs[i].position)  return i;//找到，返回顶点序号i 
	return -1;//没有找到这个顶点 
}
//3.查找并输出序号为m,n景点间的长度不超过8个景点的路径 
void path(mgraph c, int m, int n, int k)
{
	int s, t = k + 1, length = 0;//t用于存放路径上下一个顶点对应的d[]数组元素的下标 
	if (d[k] == n && k < 8)//若d[k]是终点n且景点个数<=8,则输出该路径 
	{
		for (s = 0;s < k;s++)//计算路径长度 
		{
			length = length + c.arcs[d[s]][d[s + 1]].adj;
		}
		if (length <= 100)//打印路径长度小于定长的路径 
		{
			for (s = 0;s < k;s++)//输出该路径。s=0时为起点m
			{
				printf("%d%s--->", d[s], c.vexs[d[s]].name);
			}
			printf("%d%s  ", d[s], c.vexs[d[s]].name);//输出最后一个景点名（即顶点n的名字，此时s==k）	
			printf("总路线长为%d米\n\n", length);
		}
	}
	else
	{
		s = 1;
		while (s <= c.vexnum)//从第m个顶点，试探所有顶点是否有路径 
		{
			if ((c.arcs[d[k]][s].adj < Infinity) && (visited[s] == 0))//顶点m到顶点s有边(权值不为无穷大)，且未被访问 
			{
				visited[s] = 1;
				d[k + 1] = s;//存储顶点编号 
				path(c, m, n, t);
				visited[s] = 0;//将找到的路径上顶点的访问标志重新设置为0，以用于试探新的路径 
			}
			s++;//试探从下一个顶点s开始是否有到终点的路径 
		}
	}
}
//4.查找两景点间的景点的所有路径
int allpath(mgraph c)
{
	int k, i, j, m, n;
	printf("\n\n请输入您想要查询的两个景点的编号：\n\n");
	scanf("%d%d", &i, &j);printf("\n\n");
	m = locatevex(c, i);//locatevex 确定该顶点是否存在。若存在，返回该顶点编号。 
	n = locatevex(c, j);
	d[0] = m;//存储路径起点m（int d[]数组是全局变量） 
	for (k = 0;k < key;k++)//全部顶点访问标志初值设为0 
		visited[k] = 0;
	visited[m] = 1;//第m个顶点访问标志设置为1 
	path(c, m, n, 0);//调用程序。k=1，对应起点d[1]==m。k为d[]数组下标 
	return 1;
}
//5.用迪杰斯特拉算法，求出一个景点到其他景点间的最短路径，
void shortestpath_dij(mgraph c)
{
	int v0, v, w, k = 1, min, t, p;
	int final[MaxVertexNum];//final[w]=1表示已经求得顶点V0到Vw的最短路径
	int Patharc[MaxVertexNum];//用于存储最短路径下标的数组 
	int ShortPathtable[MaxVertexNum];//用于存储到各点最短路径的权值和 
	printf("\n请输入一个起始景点的编号：");
	scanf("%d", &v0);printf("\n\n");
	while (v0<0 || v0>key)
	{
		printf("\n您输入的景点编号不存在\n");
		printf("请重新输入：");
		scanf("%d", &v0);
	}
	//初始化数据
	for (v = 1;v <= c.vexnum;v++)//数组0还是空出来 
	{
		final[v] = 0;//全部顶点初始化为未找到最短路径 
		ShortPathtable[v] = c.arcs[v0][v].adj;//将与v0点有连线的顶点加上权值 
		Patharc[v] = 0;//初始化路径数组p为0 
	}
	ShortPathtable[v0] = 0; // V0至v0的路径为0 
	final[v0] = 1;//V0至v0不需要路径 	 
	//开始主循环，每次求得V0到某个v顶点的 最短路径 
	for (v = 1;v <= c.vexnum;v++)
	{
		min = Infinity;
		for (w = 1;w <= c.vexnum;w++)//找出最近的顶点和权值 
		{
			if (!final[w] && ShortPathtable[w] < min)//有边 
			{
				k = w;
				min = ShortPathtable[w];
			}
		}
		final[k] = 1;//将目前找到的最近的顶点置1 
		//修正当前最短路径及距离
		for (w = 1;w <= c.vexnum;w++)
		{	//如果经过v顶点的路径比现在这条路径的长度短的话，更新
			if (!final[w] && (min + c.arcs[k][w].adj < ShortPathtable[w]))
			{
				ShortPathtable[w] = min + c.arcs[k][w].adj;//修改当前路径长度
				Patharc[w] = k; //存放前驱结点（像糖葫芦） 
			}
		}
	}


	printf("打印P数组:");
	for (t = 1;t <= c.vexnum;t++)
	{
		printf("%d ", Patharc[t]);
	}
	printf("\n\n");
	//打印s数组
	printf("打印S数组:");
	for (t = 1;t <= c.vexnum;t++)
	{
		printf("%d ", ShortPathtable[t]);
	}
	printf("\n\n");

	//打印最短路径
	for (t = 1;t <= c.vexnum;t++)
	{
		p = t;
		if (t != v0)//反向输出 
		{
			printf("%d%s", t, c.vexs[t].name);
			for (w = 1;w <= c.vexnum;w++)
			{
				if (Patharc[p] != 0)
				{
					printf("<--%d%s", Patharc[p], c.vexs[p].name);
					p = Patharc[p];
				}
			}
			printf("<--%d%s", v0, c.vexs[v0].name);
			printf("\n总路线长为%d米\n\n", ShortPathtable[t]);
		}
	}
}
//菜单 
void menu()
{
	printf(" *****************欢迎使用高校图书管理系统****************\n");
	printf(" │                    四川轻化工大学                     │\n");
	printf(" │                     菜 单 选 择                       │\n");
	printf(" │    1.返回菜单              2.景点信息查询             │\n");
	printf(" │    3.查询景点间最短路径     4.查询景点间所有路径      │\n");
	printf(" │    5.查看游览路线           6.修改一个已有景点        │\n");
	printf(" │    7.增加一个新景点         8.增加一条新的路径        │\n");
	printf(" │    9.删除一个景点           10.删除一条路径           │\n");
	printf(" │    0.退出                                             │\n");
	printf(" *********************************************************\n");
}
//以下是修改图的相关信息。包括建图、更新信息、删除、增加结点和边
//6.重新构造图 
int creatgraph(mgraph* c)
{
	int i, j, m, n, v0, v1, distance;
	printf("请输入图的顶点数和边数: \n");
	scanf("%d %d", &c->vexnum, &c->arcnum);
	printf("下面请输入景点的信息： \n");
	for (i = 1;i <= c->vexnum;i++)
	{
		printf("请输入景点的编号：");
		scanf("%d", &c->vexs[i].position);
		printf("\n请输入景点的名称：");
		scanf("%s", &c->vexs[i].name);
		printf("\n请输入景点的简介：");
		scanf("%s", &c->vexs[i].introduction);
		printf("\n请输入修改后景点的详细介绍:");
		scanf("%s", &c->vexs[i].super_introduction);
	}
	for (i = 1;i <= c->vexnum;i++)
		for (j = 1;j <= c->vexnum;j++)//权值全部初始化为无穷 
			c->arcs[i][j].adj = Infinity;
	printf("下面请输入图的边的信息：\n");
	for (i = 1;i <= c->vexnum;i++)
	{
		printf("\n第%d条边的起点 终点 长度为：", i);
		scanf("%d %d %d", &v0, &v1, &distance);
		m = locatevex(campus, v0);//判断一下点是否存在，存在就返回位置 
		n = locatevex(campus, v1);
		if (m > 0 && n > 0)
		{
			c->arcs[m][n].adj = distance;
			c->arcs[n][m].adj = c->arcs[m][n].adj;
		}
	}
	return 1;
}
//7.更新图的部分信息。返回值：1***比如某个信息输错了，需要改 
int newgraph(mgraph* c)
{
	int changenum;
	int i, m, n, t, distance, v0, v1;
	printf("\n下面请输入您要修改的景点的个数：\n");
	scanf("%d", &changenum);
	while (changenum<0 || changenum>key)
	{
		printf("\n输入错误！请重新输入");
		scanf("%d", &changenum);
	}
	for (i = 0;i < changenum;i++)
	{
		printf("\n请输入景点的编号：");
		scanf("%d", &m);
		t = locatevex(campus, m);
		printf("\n请输入修改后景点的名称:");
		scanf("%s", &c->vexs[t].name);
		printf("\n请输入修改后景点的简介:");
		scanf("%s", &c->vexs[t].introduction);
		printf("\n请输入修改后景点的详细介绍:");
		scanf("%s", &c->vexs[t].super_introduction);
	}
	printf("\n下面请输入您要更新的边数");
	scanf("%d", &changenum);
	while (changenum<0 || changenum>key)
	{
		printf("\n输入错误！请重新输入");
		scanf("%d", &changenum);
	}
	if (changenum != 0)
		printf("\n下面请输入更新边的信息：\n");
	for (i = 1;i <= changenum;i++)
	{
		printf("\n修改的第%d条边的起点 终点 长度为：", i);
		scanf("%d %d %d", &v0, &v1, &distance);
		m = locatevex(campus, v0);
		n = locatevex(campus, v1);
		if (m >= 0 && n >= 0)
		{
			c->arcs[m][n].adj = distance;
			c->arcs[n][m].adj = c->arcs[m][n].adj;
		}
	}
	return 1;
}
//8.增加一条边。返回值：1*** 
int enarc(mgraph* c)
{
	int m, n, distance;
	printf("\n请输入边的起点和终点编号，权值：");
	scanf("%d %d %d", &m, &n, &distance);
	while (m<0 || m>c->vexnum || n<0 || n>c->vexnum)
	{
		printf("输入错误，请重新输入：");
		scanf("%d %d", &m, &n);
	}
	if (locatevex(campus, m) < 0)
	{
		printf("此节点%d已删除", m);
		return 1;
	}
	if (locatevex(campus, n) < 0)
	{
		printf("此节点%d已被删除", n);
		return 1;
	}

	c->arcs[m][n].adj = distance;//在邻接矩阵中多加一个值 
	c->arcs[n][m].adj = c->arcs[m][n].adj;
	c->arcnum--;//图中边数+1
	return 1;
}
//9.增加一个结点。返回值：1*** 
int envex(mgraph* c)
{
	int i;
	c->vexnum++;//顶点个数+1
	printf("请输入您要增加结点的信息：");
	printf("\n编号：");
	scanf("%d", &c->vexs[c->vexnum].position);
	printf("名称：");
	scanf("%s", &c->vexs[c->vexnum].name);
	printf("简介：");
	scanf("%s", &c->vexs[c->vexnum].introduction);
	printf("详细介绍：");
	scanf("%s", &c->vexs[c->vexnum].super_introduction);

	for (i = 1;i <= c->vexnum;i++)
	{
		c->arcs[c->vexnum][i].adj = Infinity;
		c->arcs[i][c->vexnum].adj = Infinity;
	}
	return 1;
}
//10.删除图的一个顶点。返回值：1*** 
int delvex(mgraph* c)
{
	int i = 0, j;
	int m, v;
	if (c->vexnum <= 0)
	{
		printf("图中已无顶点");
		return 1;
	}
	printf("\n下面请输入您要删除的景点编号：");
	scanf("%d", &v);
	while (v<0 || v>key)
	{
		printf("\n输入错误！请重新输入:");
		scanf("%d", &v);
	}
	m = locatevex(campus, v);
	if (m < 0)
	{
		printf("此顶点%d已删除\n", v);
		return 1;
	}
	for (i = m;i <= c->vexnum - 1;i++)
		for (j = 1;j <= c->vexnum;j++)//将二维数组中的第m+1行依次向前移动一行（删除第m行） 
			c->arcs[i][j] = c->arcs[i + 1][j];
	for (i = m;i <= c->vexnum - 1;i++)
		for (j = 1;j <= c->vexnum;j++)//将二维数组中的第m+1列依次向前移动一列（删除第m列）
			c->arcs[j][i] = c->arcs[j][i + 1];
	c->vexs[v].position = -1;//表示此点已删除，后期打印也不会显示该点 
	c->vexnum--;//顶点个数-1 
	return 1;
}
//11.删除图的一条边。返回值：1*** 
int delarc(mgraph* c)
{
	int m, n, v0, v1;
	if (c->vexnum <= 0)
	{
		printf("图中已无边，无法删除。");
		return 1;
	}
	printf("\n下面请输入您要删除的边的起点和终点编号：");
	scanf("%d %d", &v0, &v1);
	m = locatevex(campus, v0);
	if (m < 0)
	{
		printf("此%d顶点已删除", v0);
		return 1;
	}
	n = locatevex(campus, v1);
	if (n < 0)
	{
		printf("此%d顶点已删除", v1);
		return 1;
	}
	c->arcs[m][n].adj = Infinity;//将删掉的边的权值改为无穷 
	c->arcs[n][m].adj = Infinity;
	c->arcnum--;//图中边数减1 
	return 1;
}
//12.输出图的邻接矩阵的值*** 
void printmatrix(mgraph c)
{
	int i, j, k = 0;
	for (i = 1;i <= key;i++)
	{
		if (c.vexs[i].position != -1)
			printf("%6d", i);//横着的标号1到11
	}
	printf("\n");
	for (i = 1;i <= c.vexnum;i++)
	{
		for (j = 1;j <= c.vexnum;j++)
		{
			if (c.arcs[i][j].adj == Infinity)
				printf(" *#@* ");
			else
				printf("%6d", c.arcs[i][j].adj);
			k++;
			if (k % c.vexnum == 0) printf("\n");
		}
	}
}
//14.查询两景点间的最短路径（floyd算法）
void floyd(mgraph c)//一种暴力破解获取最短路径的算法 
{
	int i, j, k;
	for (i = 1;i <= key;i++)//将图的邻接矩阵赋值给 shortest二维数组，将矩阵pathh全部初始化为-1 
	{
		for (j = 1;j <= key;j++)
		{
			shortest[i][j] = c.arcs[i][j].adj;
			pathh[i][j] = j;
		}
	}
	//int i1, j1, k1 = 0;
	//for (i1 = 1;i1 <= key;i1++)
	//	printf("%6d", i1);//横着的标号1到11
	//printf("\n");
	//for (i1 = 1;i1 <= key;i1++)
	//{
	//	printf("%d", i1);//竖着的标号1到11
	//	for (j1 = 1;j1 <= key;j1++)
	//	{
	//		printf("%6d", pathh[i1][j1]);
	//		k1++;
	//		if (k1 % key == 0) printf("\n");
	//	}
	//}
	//printf("\n\n\n");

	for (k = 1;k <= key;k++)//核心操作，完成了以k为中间点对所有的顶点对（i,j）进行检测和修改 
	{
		for (i = 1;i <= key;i++)
		{
			for (j = 1;j <= key;j++)
			{
				if (shortest[i][j] > shortest[i][k] + shortest[k][j])
				{
					shortest[i][j] = shortest[i][k] + shortest[k][j];
					pathh[i][j] = pathh[i][k];//记录一下所走的路 //P数组用来存放前驱顶点  
				}
			}
		}
	}
}
//15.打印出最短路径 
void printf_Pshuzu()
{
	int i, j, k = 0;
	for (i = 1;i <= key;i++)
		printf("%6d", i);//横着的标号0到11
	printf("\n");
	for (i = 1;i <= key;i++)
	{
		printf("%d", i);//竖着的标号0到11
		for (j = 1;j <= key;j++)
		{
			printf("%6d", pathh[i][j]);
			k++;
			if (k % key == 0) printf("\n");
		}
	}
	printf("\n\n\n");
}
//16.任意两点间最短距离（弗洛伊德算法）
void display(mgraph c, int i, int j)
{
	int a, b;
	a = i;b = j;
	printf("您要查询的两景点间最短路径：\n\n");
	printf("%d%s", a, c.vexs[a].name);
	while (pathh[i][j] != b)
	{
		printf("-->%d%s", pathh[i][j], c.vexs[pathh[i][j]].name);
		i = pathh[i][j];
	}
	printf("-->%d%s\n\n", b, c.vexs[b].name);
	printf("%s-->%s的最短路径是：%d 米。\n\n", c.vexs[a].name, c.vexs[b].name, shortest[a][b]);
}
//17.查询景点的信息
int shortdistance(mgraph c)
{
	int i, j;
	printf("请输入要查询的两个景点的数字编号（1->11）中间用空格间隔开。\n");
	scanf("%d %d", &i, &j);
	if (i > key || i<0 || j>key || j < 0)
	{
		printf("输入信息错误！\n\n");
		printf("请输入要查询的两个景点的数字编号（1->11）中间用空格间隔开。\n");
		scanf("%d %d", &i, &j);
	}
	else
	{
		floyd(c);printf_Pshuzu();
		display(c, i, j);
	}
	return 1;
}
void browsecompus(mgraph c)
{
	int i;
	printf(" \n\n编号        景点名称                   简介\n");
	printf("____________________________________________________________________________________________\n");
	for (i = 1;i <= key;i++)
	{
		if (c.vexs[i].position != -1)
			printf("%-10d%-25s%-80s\n", c.vexs[i].position, c.vexs[i].name, c.vexs[i].introduction);
	}
	printf("____________________________________________________________________________________________\n");
}